package exam;

/**
 * 一种数据压缩算法实现：将长字符串（称为短语）按数据编码成短小标记，用小标记代替字典中的短语。
 * 举例如下：处理"ABCBCBCBCA”字符串，输出步骤如下：
 * (0,0,A)
 * (0,0,B)
 * (0,0,C)
 * (2,2,B)
 * (4,3,A)
 * <p>
 * 压缩算法包含 一个字典缓冲区（历史缓冲器，存放前n个字符）和一个预读缓冲区（存放后n个字符）
 * <p>
 * 在字典缓冲区中寻找与预读缓冲区中的最匹配数据，如果匹配的数据长度大于最小匹配长度，那么就输出一对（当前指针的向左偏移量，匹配短语长充，下一个字符），
 * 如果未找到匹配数据，输出一对（0,0，下一个字符）。
 */
public class 压缩 {

    /**
     * 1、定义预读缓冲区、字典缓冲区
     * 2、设置字典缓冲区、输出参数
     * 3、遍历字符串，设置预读缓冲区
     * 4、判断预读缓冲区是否在 字典缓冲区里（如果不在，则输出下一个字符，）
     * 5、输出参数：第一个参数是预读缓冲区在字典缓冲区冲在的下标到字典缓冲区结束的长度；第二个参数就是预读缓冲区的长度
     * 6、如果最后一个字符在字典缓冲区里，就直接输出
     * @param s
     */
    public static void dataCompression(String s) {
        // 字典缓冲区
        String s1 = "";
        // 预读缓冲区
        String s2 = "";
        // 遍历字符
        for (int i = 0; i < s.length(); i++) {
            // 设置字典缓冲区
            s1 = s.substring(0, i);
            // 第一个输出参数
            int maxIndex = 0;
            // 第二个输出参数
            int maxNum = 0;
            // 遍历预读缓冲区
            for (int j = 0; j < s.length() - i; j++) {
                // 设置预读缓冲区
                s2 = s.substring(i, i + j + 1);
                // 判断预读缓冲区是否在 字典缓冲区里
                int index = s1.indexOf(s2);
                // 如果不在，则输出下一个字符
                if (index == -1) {
                    System.out.println("(" + maxIndex + "," + maxNum + "," + s.charAt(i + j) + ")");
                    i = i + j;
                    break;
                } else {
                    // 设置参数，第一个参数是预读缓冲区在字典缓冲区冲在的下标到字典缓冲区结束的长度
                    maxIndex = i - index;
                    // 第二个参数就是预读缓冲区的长度
                    maxNum = s2.length();
                    // 如果最后一个字符在字典缓冲区里，就直接输出。
                    if (s.length() - 1 == i) {
                        System.out.println("(" + maxIndex + "," + maxNum + "," + s.charAt(i + j) + ")");
                        break;
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        dataCompression("ABCBCBCBCA");
    }
}
